package com.wwz.leetcode;

import com.wwz.common.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: 重排链表
 * @author: Sailor
 * @date: 2023-12-18 23:24:03
 */
public class LeetCode143 {

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<>();
        // 放入容器
        while (head != null) {
            list.add(head);
            head = head.next;

        }
        int left = 0, right = list.size() - 1;
        while (left < right) {
            ListNode node = list.get(left);
            // 左边链接右边
            node.next = list.get(right);
            left++;
            if (left == right) {
                break;
            }
            // 右边去链接左边
            list.get(right).next = list.get(left);
            right--;
        }
        // 断开尾巴
        list.get(left).next = null;
    }
}
